AlphaGo要怎么变得更强？
最近互联网上最火热的话题，莫过于谷歌开发的AlphaGo计算机围棋程序与人类围棋世界冠军李世乭之间的五番棋对弈。
谷歌DeepMind的CEO Demis Hassabis。图片来源：Google Press
虽然李世乭在第四场比赛中通过几手妙棋赢得了荣誉之战，但是AlphaGo最终以4:1的比分取得了压倒性的胜利。它还能不能变得更强？本文将试图深入浅出地对AlphaGo进行分析。
围棋的棋盘共有361个落子点，规则看似简单，但是其存在的变化可以说是无穷无尽。考虑一盘棋的走子顺序大致有361！=10^768种可能，这个复杂度超过了宇宙的原子总数。所以采用最常见的遍历搜索的方式显然是不可能的。
传统的象棋和国际象棋等程序使用的基于领域专家知识和裁剪搜索的方法，在搜索空间较小时能够成功，但在下围棋时特别容易把最优路径裁掉，因而进展不大。1993年，物理学家Bernd Brügmann中第一次提出使用Monte Carlo方法设计围棋程序Gobble[1]。他引入了一个重要的概念：随机比赛直至结束（Playout），这个概念成为Monte Carlo方法的核心。他的方法特别简单：使用随机掷骰子直到决出胜负，然后根据胜负比例调整下棋步骤——这是第一个纯粹依据概率统计而不是人工定义规则的围棋程序。在受让2子的情况下，Gobble和当时最好的围棋程序Many Faces of Go几乎打成平手。
2006年，法国人Rémi Coulom提出了一种新的基于树的Monte Carlo围棋算法[2]，把树搜索和Monte Carlo方法结合起来，通过主动扩展树而不是裁剪树（在此之前的树算法和Monte Carlo结合算法的策略）从而避免了因裁剪带来的剪枝损失，在模拟棋局趋于无穷的时候，能够保证收敛到最优解。他还参考N臂老虎机问题引入了平滑概率概念，从而使得一步棋的概率永远不为零（前几步的坏棋在和后几步的好棋结合以后可能会变成好棋，此策略会保留前几步的坏棋），再引入了一种鲁棒的收益反传函数，有效控制了模拟数目变化时系统的稳定性。
Rémi Coulom开发的围棋AI CrazyStone。图片来源：remi-coulom.fr
Coulom开发出的CrazyStone成功战胜了同样基于Monte Carlo算法的Indigo（胜率61%）。但它还是不如基于专家知识和规则的GNU Go（胜率30%）。经过改进，CrazyStone成为此前围棋程序中效果最好的程序，其在2013年受让4子的情况下，在19*19标准棋盘上战胜了有”人类计算机“之称的日本围棋九段石田芳夫。
直到今年，Google DeepMind让大家大吃一惊。其在1月28日的《自然》杂志上发表文章[3]宣布他们的围棋程序AlphaGo战胜欧洲围棋冠军樊麾。一个多月后，AlphaGo又以AlphaGo 4:1战胜韩国九段棋手李世乭。
DeepMind的CEO Demis Hassabis宣传称DeepMind是在2014年开始做围棋程序的。但我们分析认为，真正的起始时间点应该是在2012年6月到12月。自然上关于AlphaGo的论文有两位第一作者：David Silver和Aja Huang（黄士杰），他们都在加拿大阿尔伯塔大学呆过——这所大学有一个世界知名的围棋研发组（组内的Martin Muller教授更是研究围棋达到30年之久）。2012年，David Silver前脚刚去DeepMind，黄士杰后脚也就过去了（博士后刚做了一年），我们推测2012年DeepMind已经在筹划围棋，并招兵买马。
David Silver（左二）与黄士杰（右二）同在2012年加入DeepMind。图片来源：Google Press
2
AlphaGo的设计结合了传统的蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）方法和最新的深层卷积神经网络（Deep ConvolutionalNeural Networks, DCNN）。通过引入策略网络（Policy network）和估值网络（Value network）模块，AlphaGo具有了和人一样的大局观和棋感，能够不拘泥于局部盈亏；同时，借鉴MCTS策略，AlphaGo具备了深达40步的超强运算能力。
微软亚洲研究院介绍了AlphaGo的工作机理[5]，同时也分析了被外界广为推崇的自对弈策略，认为自对弈策略存在明显天花板，提升有限。
AlphaGo在对弈时是这么做的：
首先根据当前落子情况，提取全局特征并送入策略网络以估计出在棋盘各个空地落子的概率（图1）。
之后，以策略网络估计出的初始落子概率为基础，重点针对落子概率较高的点来继续计算该点往下发展权重，这里通过估值网络估计（图2）和快速走棋（Fast rollout）的方式来估计该点落子后、模拟走棋到最后的赢面如何，并根据这个模拟走棋的输赢概率反过来调整当前落子的权重。
之后，进一步结合MCTS搜索实现对后续更多步数的相关概率计算；最后综合上述各流程的概率得分形成对当前步落子的最终决策。
然而，围棋界专业人士也指出了AlphaGo存在几个问题：开局相对水平比较低，中段实力超群，面对复杂局面和打劫稍有不足（第四局输棋原因）。为什么会有这些局限，又能怎么改进呢？
大部分人认为Google收集了3000万棋局，同时使用自对弈生成了3000万棋局。实际上，Google只收集了16万人类对弈棋局。这16万棋局，按手可以拆分为3000万个盘面，Google用这3000万个盘面来训练策略网络和估值网络。对于策略网络来说，16万盘相当于3000万训练数据；但对于估值网络来说，由于估值网络的目标是终局胜负， 16万盘数据只相当于16万个训练数据，这就导致估值网络训练数据极度稀缺。
Google用这3000万个盘面来训练策略网络和估值网络。图片来源：Nature
有鉴于此，我们认为Google使用自对弈策略是“被逼”的：Google也曾尝试在策略网络训练中使用自对弈，但是未获得成功，因为自对弈常常走出比较窄的棋路，而实战中算法面对棋路比较发散的人类时则不具备优势，尽管在自我对弈中，基于自对弈棋局训练的网络战绩更好（甚至面对其他围棋程序时，也是自对弈网络更好）。最终Google在和人对战中抛弃了基于自对弈的强化版策略网络。
自对弈对策略网络训练帮助不大的原因是：策略网络是基于单手盘面训练的，而同一局棋局中的前后盘面的训练目标不一样，一个对局可以按手拆分为数百盘面，总共3000万个盘面训练数据已经足够让DCNN的训练得以有效进行而不会发生过训练（Over-fitting）现象。
但是估值网络的训练则有很大的不同：估值网络的目标是一局棋的结果，因此对于同一局棋，所有拆分出来的盘面的目标都是一样的，这样实际有效训练样本数目只有16万，对于训练较大复杂度的DCNN（例如十几层、每一层有数百Feature Map的配置）则显得太少了，容易发生过训练问题。这在Google的Nature论文上也有所体现：如果仅使用人类对弈棋局，那么DCNN估值网络的训练集合误差是0.19，而在测试集合的误差高达0.37。这个现象如果用模式识别的语言来解读的话，就是“模型训练过度拟合了训练数据并获得了一个失败的模型，该模型在未知测试集上的推广性比较差”。
针对上述训练估值网络中碰到的问题，Google团队给出了一个比较聪明的解决方案：自对弈，这个自对弈是一个设计巧妙的数据生成系统，而不是真正的自我提升的自对弈。这个方案是AlphaGo的重要创新之一。
图3，根据Nature论文梳理出来的自对弈生成估值网络的比赛的流程。
可以看到，首先我们要用普通策略网络来生成一个起始盘面（这个盘面是根据最开始的随机数U确定步骤为U-1）。然后再通过随机走一步来引入更多盘面，最后才是自对弈过程。对弈完成后，对弈过程中的盘面被抛弃（这个盘面可能会比较单一，而且和实际人人或人机对弈棋局差异很大），只留下对弈的第一步行程的棋局盘面作为训练的输入，而对弈最后的胜负作为训练目标——这实际上是一个非常粗糙的数据生成器，而并非很多外行所谓的“双手互搏”，无中生有。实际上，对弈的过程是被抛弃的。这是为了解决实际人类对弈棋局太少从而导致数据极其稀疏，最终导致估值网络无法训练而引入的数据增强策略。
但这是一个很巧妙的策略，可以极大增加训练数据，而且，通过随机化带来盘面变化，从而使得对弈接近人类对局。但是我们认为这种扩充数据的方案是可以改进的。实际上，引入估值网络，能提升等级分400分左右，这说明了估值网络的价值。反过来，引入策略网络可以提升等级分一千多分，暗示估值网络的训练可能还有改进空间。
借鉴该训练过程，我们认为AlphaGo目前可能存在的缺陷，如复杂盘面的应对和打劫的处理，能得到改进。我们认为可以通过自对弈来模拟以打劫为代表的特殊或复杂盘面，从而产生很多复杂盘面和打劫盘面，然后再训练对应的估值网络，有可能提升估值的精度。
开局时，围棋算法的性能不佳很容易理解——此时，策略网络和估值网络的输入都极为有限，同时，基于MCTS的走子理论深度最深，这些都导致AlphaGo的战力受损。
参考图像识别的思路，我们认为可以考虑在开局阶段通过模糊化盘面来提升性能，可以设计专门针对开局的策略网络和估值网络，在开局网络中，不以19*19分辨率为预测目标，而以模糊化（如5*5,9*9等）图像为预测目标。这样做。一来可以简化模型复杂度，二来可以增加落子鲁棒性，当然这个网络需要和普通网络结合起来才能取得更好的效果。
围棋曾被认为是计算机不可能完成的任务，但AlphaGo在引入深度神经网络以后，围棋程序第一次具有了大局观和形势判决这种人类独有的“直觉”，并战胜了人类选手；这是科学的进步，也是人类的胜利。
实际上，近年来在很多以前人类独有的智能上，机器都有了长足的进步，比如语音识别、图像识别等。这次AlphaGo在围棋上突破的象征意义大于实际意义，毕竟深度学习从2011年开始就已经深入人心了。而这次的突破更多地局限于围棋本身，因为这些算法早已广为人知。
多少年来，人类一直在追求真正人工智能的道路上努力前行。随着以语音和图像为代表的感知智能领域、以及以围棋为代表的特殊专业领域不断获得突破，人类也对人工智能寄予着新的期望：希望机器具备理解能力、思考能力、推理能力，甚至是创造能力和进化能力。
然而，真正实现强人工智能的道路还很远，举例而言，自然语言理解就是目前的一个最大障碍。有一个知名的测试叫”Winograd Schema”，它的一个问题如下“父亲举不动他的孩子因为他太重了，请问是他指的是父亲还是孩子”，机器目前在回答这种偏常识性的问题上非常吃力。
目前业界公认的人工智能的下一个重要堡垒就是自然语言理解，我们希望在这个里程碑的节点上，我们能够静下心来，朝着下一个山峰进发，实现真正的人工智能。
（编辑、排版：Calo）
参考文献：
[1] Brügmann B. Monte carlogo[R]. Syracuse, NY: Technical report, Physics Department, Syracuse University,1993.
[2] Coulom R. Efficientselectivity and backup operators in Monte-Carlo tree search[M]. Computers andgames. Springer Berlin Heidelberg, 2006: 72-83.
[3] Silver D, Huang A,Maddison C J, et al. Mastering the game of Go with deep neural networks andtree search[J]. Nature, 2016, 529（7587）: 484-489.
[4] Huang S C. Newheuristics for Monte Carlo tree search applied to the game of go[D]. Ph. D.dissertation, Nat. Taiwan Normal Univ., Taipei, 2011.
[5] 郑宇张钧波：“一张图解AlphaGo原理及弱点”。
本文来自果壳网，谢绝转载
如有需要请联系sns@guokr.com
围棋AI赢了，人类输了吗？
点击“阅读原文”，你会看到不一样的观点